package chapter01;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FourSum {
    //去重+双指针
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new LinkedList<>();
        int left,right,sum;
        if(nums.length<4){
            return list;
        }
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.length;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                left=j+1;
                right=nums.length-1;
                while(left<right){
                    if((long)nums[i]+nums[j]+nums[left]+nums[right]==target){
                        List<Integer> member=new LinkedList<>();
                        member.add(nums[i]);
                        member.add(nums[j]);
                        member.add(nums[left]);
                        member.add(nums[right]);
                        list.add(member);
                        left++;
                        while(left<right&&nums[left]==nums[left-1]){
                            left++;
                        }
                        right--;
                        while(left<right&&nums[right]==nums[right+1]){
                            right--;
                        }
                    }else if((long)nums[i]+nums[j]+nums[left]+nums[right]<target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(new FourSum().fourSum(new int[]{2,2,2,2,2},8));
    }
}
